package com.yiguang.algorithm.dfs;


public class DFSTest {
	
	public static void main(String[] args) {
		TreeNode shiyi = new TreeNode(11);
		TreeNode jiu = new TreeNode(9, null, shiyi);
		TreeNode liu = new TreeNode(6, null, jiu);
		TreeNode shi = new TreeNode(10);
		TreeNode qi = new TreeNode(7, null, shi);
		TreeNode san = new TreeNode(3, liu, qi);
		TreeNode ba = new TreeNode(8);
		TreeNode si = new TreeNode(4, ba, null);
		TreeNode wu = new TreeNode(5);
		TreeNode er = new TreeNode(2, si, wu);
		TreeNode yi = new TreeNode(1, er, san);
		
		DFSTest test = new DFSTest();
		int result = test.minDepth2(yi);
		System.out.println(result);
	}
	
	/**
		111. 二叉树的最小深度
		给定一个二叉树，找出其最小深度。
	
		最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
	
		说明：叶子节点是指没有子节点的节点。
	*/
	public int minDepth2(TreeNode root) {
        if(root==null) {
        	return 0;
        }
        if(root.left==null && root.right==null) {
        	return 1;
        }
        int minDepth = Integer.MAX_VALUE;
        if(root.left!=null) {
        	minDepth = Math.min(minDepth2(root.left)+1, minDepth);
        }
        if(root.right!=null) {
        	minDepth = Math.min(minDepth2(root.right)+1, minDepth);
        }
        return minDepth;
    }
	
	public int minDepth(TreeNode root) {
        if(root==null) {
        	return 0;
        }
        if(root.left==null && root.right==null) {
        	return 1;
        }
        int depth = 1;
        int reulst = backtrack(root, depth);
        return reulst;
    }
	
	public int backtrack(TreeNode root, int depth) {
		int left = depth;
		int right = depth;
		if(root.left!=null) {
			left = backtrack(root.left, depth+1);
        }
        if(root.right!=null) {
        	right = backtrack(root.right, depth+1);
        }
        if(root.left==null) {
        	return right;
        }
        if(root.right==null) {
        	return left;
        }
        if(left < right) {
        	return left;
        }
        return right;
	}

}

class TreeNode {
    int val;
    TreeNode left; 
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}